home *** CD-ROM | disk | FTP | other *** search
/ The Fatted Calf / The Fatted Calf.iso / Unix / CNews / Source / libc / hdbm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-03-03  |  6.2 KB  |  277 lines
  1. /*
  2.  * general-purpose in-core hashing, dbm interface
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include "hdbm.h"
  9. #include "hdbmint.h"
  10.  
  11. /* tunable parameters */
  12. #define RETAIN 300        /* retain & recycle this many HASHENTs */
  13.  
  14. /* fundamental constants */
  15. #define YES 1
  16. #define NO 0
  17.  
  18. static HASHENT *hereuse = NULL;
  19. static int reusables = 0;
  20.  
  21. static unsigned                /* not yet taken modulus table size */
  22. hdbmdef(key)
  23. HDBMDATUM key;
  24. {
  25.     register char *s = key.dat_ptr;
  26.     register unsigned len = key.dat_len;
  27.     register unsigned hash = 0;
  28.  
  29.     while (len-- > 0)
  30.         hash += *s++;
  31.     return hash;
  32. }
  33.  
  34. HASHTABLE *
  35. hdbmcreate(size, hashfunc)
  36. register unsigned size;            /* a crude guide to size */
  37. unsigned (*hashfunc)();
  38. {
  39.     register HASHTABLE *tbl;
  40.     register HASHENT **hepp;
  41.     /*
  42.      * allocate HASHTABLE and (HASHENT *) array together to reduce the
  43.      * number of malloc calls.  this idiom ensures correct alignment of
  44.      * the array.
  45.      * dmr calls the one-element array trick `unwarranted chumminess with
  46.      * the compiler' though.
  47.      */
  48.     register struct alignalloc {
  49.         HASHTABLE ht;
  50.         HASHENT *hepa[1];    /* longer than it looks */
  51.     } *aap;
  52.  
  53.     aap = (struct alignalloc *)
  54.         malloc(sizeof *aap + (size-1)*sizeof(HASHENT *));
  55.     if (aap == NULL)
  56.         return NULL;
  57.     tbl = &aap->ht;
  58.     tbl->ht_size = (size == 0? 1: size);    /* size of 0 is nonsense */
  59.     tbl->ht_magic = HASHMAG;
  60.     tbl->ht_hash = (hashfunc == NULL? hdbmdef: hashfunc);
  61.     tbl->ht_addr = hepp = aap->hepa;
  62.     while (size-- > 0)
  63.         hepp[size] = NULL;
  64.     return tbl;
  65. }
  66.  
  67. /*
  68.  * free all the memory associated with tbl, erase the pointers to it, and
  69.  * invalidate tbl to prevent further use via other pointers to it.
  70.  */
  71. hdbmdestroy(tbl)
  72. register HASHTABLE *tbl;
  73. {
  74.     register unsigned idx;
  75.     register HASHENT *hp, *next;
  76.     register HASHENT **hepp;
  77.     register int tblsize;
  78.  
  79.     if (tbl == NULL || BADTBL(tbl))
  80.         return;
  81.     tblsize = tbl->ht_size;
  82.     hepp = tbl->ht_addr;
  83.     for (idx = 0; idx < tblsize; idx++) {
  84.         for (hp = hepp[idx]; hp != NULL; hp = next) {
  85.             next = hp->he_next;
  86.             hp->he_next = NULL;
  87.             hefree(hp);
  88.         }
  89.         hepp[idx] = NULL;
  90.     }
  91.     tbl->ht_magic = 0;        /* de-certify this table */
  92.     tbl->ht_addr = NULL;
  93.     free((char *)tbl);
  94. }
  95.  
  96. /*
  97.  * The returned value is the address of the pointer that refers to the
  98.  * found object.  Said pointer may be NULL if the object was not found;
  99.  * if so, this pointer should be updated with the address of the object
  100.  * to be inserted, if insertion is desired.
  101.  */
  102. static HASHENT **
  103. hdbmfind(tbl, key)
  104. register HASHTABLE *tbl;
  105. HDBMDATUM key;
  106. {
  107.     register HASHENT *hp, *prevhp = NULL;
  108.     register char *hpkeydat, *keydat = key.dat_ptr;
  109.     register int keylen = key.dat_len;
  110.     register HASHENT **hepp;
  111.     register unsigned size; 
  112.  
  113.     if (BADTBL(tbl))
  114.         return NULL;
  115.     size = tbl->ht_size;
  116.     if (size == 0)            /* paranoia: avoid division by zero */
  117.         size = 1;
  118.     hepp = &tbl->ht_addr[(*tbl->ht_hash)(key) % size];
  119.     for (hp = *hepp; hp != NULL; prevhp = hp, hp = hp->he_next) {
  120.         hpkeydat = hp->he_key.dat_ptr;
  121.         if (hp->he_key.dat_len == keylen && hpkeydat[0] == keydat[0] &&
  122.             memcmp(hpkeydat, keydat, keylen) == 0)
  123.             break;
  124.     }
  125.     /* assert: *(returned value) == hp */
  126.     return (prevhp == NULL? hepp: &prevhp->he_next);
  127. }
  128.  
  129. static HASHENT *
  130. healloc()                    /* allocate a hash entry */
  131. {
  132.     register HASHENT *hp;
  133.  
  134.     if (hereuse == NULL)
  135.         return (HASHENT *)malloc(sizeof(HASHENT));
  136.     /* pull the first reusable one off the pile */
  137.     hp = hereuse;
  138.     hereuse = hereuse->he_next;
  139.     hp->he_next = NULL;            /* prevent accidents */
  140.     reusables--;
  141.     return hp;
  142. }
  143.  
  144. static
  145. hefree(hp)                    /* free a hash entry */
  146. register HASHENT *hp;
  147. {
  148.     if (reusables >= RETAIN)        /* compost heap is full? */
  149.         free((char *)hp);        /* yup, just pitch this one */
  150.     else {                    /* no, just stash for reuse */
  151.         ++reusables;
  152.         hp->he_next = hereuse;
  153.         hereuse = hp;
  154.     }
  155. }
  156.  
  157. int
  158. hdbmstore(tbl, key, data)
  159. register HASHTABLE *tbl;
  160. HDBMDATUM key, data;
  161. {
  162.     register HASHENT *hp;
  163.     register HASHENT **nextp;
  164.  
  165.     if (BADTBL(tbl))
  166.         return NO;
  167.     nextp = hdbmfind(tbl, key);
  168.     if (nextp == NULL)
  169.         return NO;
  170.     hp = *nextp;
  171.     if (hp == NULL) {            /* absent; allocate an entry */
  172.         hp = healloc();
  173.         if (hp == NULL)
  174.             return NO;
  175.         hp->he_next = NULL;
  176.         hp->he_key = key;
  177.         *nextp = hp;            /* append to hash chain */
  178.     }
  179.     hp->he_data = data;    /* supersede any old data for this key */
  180.     return YES;
  181. }
  182.  
  183. /* return any existing entry for key; otherwise call allocator to make one */
  184. HDBMDATUM
  185. hdbmentry(tbl, key, allocator)
  186. register HASHTABLE *tbl;
  187. HDBMDATUM key;
  188. HDBMDATUM (*allocator)();
  189. {
  190.     register HASHENT *hp;
  191.     register HASHENT **nextp;
  192.     static HDBMDATUM errdatum = { NULL, 0 };
  193.  
  194.     if (BADTBL(tbl))
  195.         return errdatum;
  196.     nextp = hdbmfind(tbl, key);
  197.     if (nextp == NULL)
  198.         return errdatum;
  199.     hp = *nextp;
  200.     if (hp == NULL) {            /* absent; allocate an entry */
  201.         hp = healloc();
  202.         if (hp == NULL)
  203.             return errdatum;
  204.         hp->he_next = NULL;
  205.         hp->he_key = key;
  206.         hp->he_data = (*allocator)(key);
  207.         *nextp = hp;            /* append to hash chain */
  208.     }
  209.     return hp->he_data;
  210. }
  211.  
  212. int
  213. hdbmdelete(tbl, key)
  214. register HASHTABLE *tbl;
  215. HDBMDATUM key;
  216. {
  217.     register HASHENT *hp;
  218.     register HASHENT **nextp;
  219.  
  220.     nextp = hdbmfind(tbl, key);
  221.     if (nextp == NULL)
  222.         return NO;
  223.     hp = *nextp;
  224.     if (hp == NULL)                /* absent */
  225.         return NO;
  226.     *nextp = hp->he_next;            /* skip this entry */
  227.     hp->he_next = NULL;
  228.     hp->he_data.dat_ptr = hp->he_key.dat_ptr = NULL;
  229.     hefree(hp);
  230.     return YES;
  231. }
  232.  
  233. HDBMDATUM                    /* data corresponding to key */
  234. hdbmfetch(tbl, key)
  235. register HASHTABLE *tbl;
  236. HDBMDATUM key;
  237. {
  238.     register HASHENT *hp;
  239.     register HASHENT **nextp;
  240.     static HDBMDATUM errdatum = { NULL, 0 };
  241.  
  242.     if (BADTBL(tbl))
  243.         return errdatum;
  244.     nextp = hdbmfind(tbl, key);
  245.     if (nextp == NULL)
  246.         return errdatum;
  247.     hp = *nextp;
  248.     if (hp == NULL)                /* absent */
  249.         return errdatum;
  250.     else
  251.         return hp->he_data;
  252. }
  253.  
  254. /*
  255.  * visit each entry by calling nodefunc at each, with key, data and hook as
  256.  * arguments.  hook is an attempt to allow side-effects and reentrancy at
  257.  * the same time.
  258.  */
  259. hdbmwalk(tbl, nodefunc, hook)
  260. HASHTABLE *tbl;
  261. register int (*nodefunc)();
  262. register char *hook;                /* (void *) really */
  263. {
  264.     register unsigned idx;
  265.     register HASHENT *hp;
  266.     register HASHENT **hepp;
  267.     register int tblsize;
  268.  
  269.     if (BADTBL(tbl))
  270.         return;
  271.     hepp = tbl->ht_addr;
  272.     tblsize = tbl->ht_size;
  273.     for (idx = 0; idx < tblsize; idx++)
  274.         for (hp = hepp[idx]; hp != NULL; hp = hp->he_next)
  275.             (*nodefunc)(hp->he_key, hp->he_data, hook);
  276. }
  277.